package q386_lexicalOrder;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /*
    此题对字典序比较了解
    对于字典序的排序
    例如我们输入101
    那么排序应该是
    1 10 100 101 11 12
    而不是
    1 10 11 12。。 100 101
     */
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ret = new ArrayList<>();
        int number = 1;
        for (int i = 0; i < n; i++) {
            // 预先先加入数字
            ret.add(number);
            if (number * 10 <= n) {
                // 首先判断number * 10是否符合条件
                number *= 10;
            } else {
                // 如果不符合条件 先判断是否有number % 10 == 9 || number + 1 > n
                // 如果满足 那么说明末尾的数位已经搜索完成，退回上一位
                while (number % 10 == 9 || number + 1 > n) {
                    number /= 10;
                }
                // 然后再开始number++
                number++;
            }
        }
        return ret;

    }
}
